package leetcode.editor.cn;


/**
 * @author: yangwk
 * @date: 2023/10/19
 * @description:
 **/
public class P481 {
    /**
     * A magical string s consists of only '1' and '2' and obeys the following rules:
     * <p>
     * The string s is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string s itself.
     * The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......"
     * and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.
     * Given an integer n, return the number of 1's in the first n number in the magical string s.
     *
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(magicalString(100));
    }

    public static int magicalString(int n) {
        StringBuilder str = new StringBuilder("12");
        int count = str.length() - 1;
        int cur = str.length() - 1;
        boolean wait = true;
        while (str.length() < n) {
            //122112122122112 1122
            //122112122122112 11221
            //1 2 211 21 2 21  2 2
            if (str.charAt(count) == '2') {
                if (str.charAt(cur) == '2') {
                    if (wait) {
                        str.append('2');
                        wait = false;
                        cur++;
                        count++;
                    } else {
                        str.append('1').append('1');
                        cur += 2;
                        count++;
                    }
                } else if (str.charAt(cur) == '1') {

                    if (wait) {
                        str.append('1');
                        wait = false;
                        cur++;
                        count++;
                    } else {
                        str.append('2').append('2');
                        wait = false;
                        cur += 2;
                        count++;
                    }
                }
            } else if (str.charAt(count) == '1') {
                 if (str.charAt(cur) == '1') {
                    str.append('2');
                    cur++;
                    count++;
                }else{
                     str.append('1');
                     cur++;
                     count++;
                 }
            }
        }

        int index = 0;
        int num = 0;
        while (index < n) {
            if (str.charAt(index) == '1') {
                num++;
            }
            index++;
        }
        return num;

    }


}
